Spark (mathematics)

In mathematics, specifically in linear algebra, the spark of a matrix A is the smallest number n such that there exists a set of n columns in A which are linearly dependent. Formally,

$\mathrm{spark}(A) = \min_{d \ne 0} \|d\|_0 \text{ s.t. } A d = 0.$

By contrast, the rank of a matrix is the smallest number k such that all sets of k + 1 columns in A are linearly dependent.

The concept of the spark is of use in the theory of compressive sensing, where requirements on the spark of the measurement matrix are used to ensure stability and consistency of various estimation techniques.

References

Donoho, David L.; Elad, Michael (March 4, 2003), "Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ¹ minimization", Proc. Nat. Acad. Sci. 100 (5): 2197–2202, doi:10.1073/pnas.0437847100, PMC 153464, PMID 16576749, http://www.pnas.org/cgi/doi/10.1073/pnas.0437847100